package day001;

import java.util.Arrays;

import static common.Utils.*;
public class Code08_QuickSort {

    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }

        quickSort(arr, 0, arr.length -1);

    }

    public static void quickSort(int[] arr, int L, int R){
        if(L < R){
            // 随机选取划分值，和最右边值交换
            swap(arr, L + (int) (Math.random() * (R-L+1)), R);
            int[] p = partition(arr,L, R);
            quickSort(arr, L, p[0] -1);   // 小于区域递归
            quickSort(arr, p[1] +1, R);   // 大于区域递归
        }
    }

    public static int[] partition(int[] arr, int L, int R){

        int less = L - 1; //小于区域 最左侧下标
        int more = R;     //大于区域 最右侧下标

        while(L < more){  // L 当前值，arr[R] 划分值
            if(arr[L] < arr[R]){
                swap(arr, L++, ++less);
            }else if(arr[L] > arr[R]){
                swap(arr, L, --more);
            }else{
                L++;
            }
        }
        swap(arr, more, R); //最后一步把   划分值与最大值前一个交换
        return new int[] {less + 1, more};
    }

    public static void main(String[] args) {
        int testTimes = 50000;
        int maxValue = 100;
        int maxSize = 100;
        boolean succeed = true;
        for(int i = 0; i < testTimes; i++){
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            quickSort(arr1);
            compareArr(arr2);
            if(!Arrays.equals(arr1,arr2)){
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice" : "wrong");

    }
}
